package gold.digger;

import gold.utils.InputUtil;
import gold.utils.UF;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC749 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        int[][] grid;
        int m, n;
        int willCount = 0; // 即将感染的格子
        int wallCount = 0; // 每次需的隔离墙的数量
        int[][] direct = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int res = 0;

        public int containVirus(int[][] isInfected) {
            grid = isInfected;
            m = isInfected.length;
            n = isInfected[0].length;
            List<Region> regions = find();
            while (regions.size() > 0) {
                int idx = 0;
                int maxWillCount = 0;
                for (int i = 0; i < regions.size(); i++) {
                    int c = regions.get(i).willInfectedCount;
                    if (c > maxWillCount) {
                        idx = i;
                        maxWillCount = c;
                    }
                }
                for (int i = 0; i < regions.size(); i++) {
                    Region region = regions.get(i);
                    if (idx == i) updateBlockadedDfs(region.infected, region.i, region.j);
                    else updateInfectedDfs(region.infected, region.i, region.j);
                    System.out.println();
                }
                res += regions.get(idx).wallCount;
                regions = find();
            }
            return res;
        }

        // 封锁
        private void updateBlockadedDfs(int[][] temp, int i, int j) {
            if (i < 0 || j < 0 || i >= m || j >= n) return;
            //  已经遍历的        且  需要封锁
            if (temp[i][j] == 2) {
                grid[i][j] = -1;
                temp[i][j] = -1;
                for (int[] ints : direct) {
                    updateBlockadedDfs(temp, i + ints[0], j + ints[1]);
                }
            }
        }

        // 感染
        private void updateInfectedDfs(int[][] temp, int i, int j) {
            if (i < 0 || j < 0 || i >= m || j >= n) return;
            boolean flag = temp[i][j] == 3;
            //  已经遍历的        或 要感染的
            if (temp[i][j] == 2 || temp[i][j] == 3) {
                grid[i][j] = 1;
                temp[i][j] = 1;
                if (!flag)
                    for (int[] ints : direct) {
                        updateInfectedDfs(temp, i + ints[0], j + ints[1]);
                    }
            }
        }

        private List<Region> find() {
            List<Region> list = new ArrayList<>();
            // 1. 统计所有病毒感染的区域
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1) {
                        int[][] temp = copyGrid(grid); // 2: 访问过的病毒区域 3: 未来要变成的病毒区域
                        dfs(temp, i, j);
                        // 构建region
                        Region region = new Region();
                        region.i = i;
                        region.j = j;
                        region.infected = temp;
                        region.wallCount = wallCount;
                        region.willInfectedCount = willCount;
                        list.add(region);
                        willCount = 0;
                        wallCount = 0;
                    }
                }
            }
            return list;
        }

        private int[][] copyGrid(int[][] grid) {
            int[][] temp = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    temp[i][j] = grid[i][j];
                }
            }
            return temp;
        }

        // 每次遍历
        // 把temp的当前访问的病毒区域，访问过的设置为2，即将访问的设置为3
        // 把grid的当前访问的病毒区域，访问过的设置为2
        private void dfs(int[][] temp, int i, int j) {
            if (i < 0 || j < 0 || i >= m || j >= n) return;
            if (temp[i][j] == 0 || temp[i][j] == 3) wallCount++;
            if (temp[i][j] == 0) {
                willCount++;
                temp[i][j] = 3;
            } else if (temp[i][j] == 1) {
                temp[i][j] = 2;
                grid[i][j] = 2;
                for (int k = 0; k < direct.length; k++) {
                    dfs(temp, i + direct[k][0], j + direct[k][1]);
                }
            }
        }

        class Region {
            int i;
            int j;
            int[][] infected; // 感染情况 2: 访问过的病毒区域 3: 未来要变成的病毒区域
            int willInfectedCount; // 将要感染的区域的数量
            int wallCount; // 需要用的隔离墙的数量
        }

    }

    class Solution_Too_Complicated_No_Want_to_Write {


        /**
         * Created by fanzhenyu02 on 2020/6/27.
         * Union Find 算法实现
         */
        public class UF {
            // 连通分量个数
            private int count;
            // 存储一棵树
            private int[] parent;
            // 记录树的“重量”
            private int[] size;

            public UF(int n) {
                this.count = n;
                parent = new int[n];
                size = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                    size[i] = 1;
                }
            }

            /* 将 p 和 q 连接 */
            public void union(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                if (rootP == rootQ)
                    return;

                // 小树接到大树下面，较平衡
                if (size[rootP] > size[rootQ]) {
                    parent[rootQ] = rootP;
                    size[rootP] += size[rootQ];
                } else {
                    parent[rootP] = rootQ;
                    size[rootQ] += size[rootP];
                }
                count--;
            }

            /* 判断 p 和 q 是否连通 */
            public boolean connected(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                return rootP == rootQ;
            }

            private int find(int x) {
                while (parent[x] != x) {
                    // 进行路径压缩
                    parent[x] = parent[parent[x]];
                    x = parent[x];
                }
                return x;
            }

            /* 返回图中有多少个连通分量 */
            public int count() {
                return count;
            }

            /* 返回图中联通集合 */
            public Map<Integer, List<Integer>> outputAggregateSet(int n) {
                Map<Integer, List<Integer>> aggregateMap = new HashMap<>();

                // 共有n个集合
                for (int i = 0; i < n; i++) {
                    int parentId = find(i);
                    if (!aggregateMap.containsKey(parentId)) aggregateMap.put(parentId, new ArrayList<>());
                    aggregateMap.get(parentId).add(i);
                }

                System.out.println(aggregateMap.toString());
                return aggregateMap;
            }
        }

        int m = 0, n = 0;

        public int containVirus(int[][] isInfected) {
            m = isInfected.length;
            n = isInfected[0].length;

            Map<Integer, Integer> neiMap = new HashMap<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {

                }
            }

            return 1;
        }
    }

    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC749 an = new LC749();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
